Ngay từ tháng 8 năm 1945, lực lượng Công an đã được thành lập chưa có tên gọi chung: ở Bắc Bộ có tên là Sở Liêm phóng, ở Trung Bộ là Sở trinh sát và ở Nam Bộ là Quốc gia tự vệ cuộc. Ngày 19 tháng 8 năm 1945 được coi là ngày thành lập ngành Công an Việt Nam.[3]

Ngày 21-2-1946, Chủ tịch Hồ Chí Minh ký Sắc lệnh số 23/SL hợp nhất Sở Cảnh sát và Sở Liêm phóng toàn quốc thành một cơ quan đặt tên là Việt Nam Công an vụ, đặt dưới quyền quản lý của Bộ Nội vụ. Giám đốc đầu tiên của Việt Nam Công an vụ là Nguyễn Dương (từ ngày 22 tháng 3 đến ngày 7 tháng 6 năm 1946).[4] Sau đó Phó Giám đốc Việt Nam Công an vụ Lê Giản lên thay.[5]

Ngày 18 tháng 4 năm 1946, Bộ Nội vụ ra Nghị định số 121-NV/NĐ về tổ chức Việt Nam Công an vụ có 3 cấp:[5]

• Cấp trung ương gọi là Nha Công an Trung ương[5]
• Cấp kỳ có tên gọi là Sở Công an kỳ[5]
• Cấp tỉnh có tên gọi là Ty Công an tỉnh, thành phố[5]

Thực hiện Sắc lệnh số 23/SL, ở Bắc Bộ, Sở Liêm phóng đổi thành Sở Công an Bắc Bộ; ở Trung Bộ, Sở Trinh sát đổi thành Sở Công an Trung Bộ; Quốc gia Tự vệ Cuộc Nam Bộ đổi thành Sở Công an Nam Bộ. Ở các tỉnh và thành phố đều đổi thành Ty Công an. Từ sau khi có Sắc lệnh 23-SL đến ngày Toàn quốc Kháng chiến, Nha Công an Việt Nam có ba bộ phận chủ yếu (Văn phòng, Ty tập trung tài liệu, Ty thanh tra).

Trong kháng chiến chống Pháp, Nha Công an Trung ương đóng tại thung lũng Lũng Cò, thôn Đồng Đon, xã Minh Thanh, huyện Sơn Dương, tỉnh Tuyên Quang. Tại đây có các cơ quan trực thuộc như Ty tình báo, Ty trật tự tư pháp, Ty chính trị. Giám đốc Nha Công an đầu tiên là Lê Giản. Đến tháng 8 năm 1952, Trần Quốc Hoàn thay Lê Giản làm Giám đốc Nha Công an.

Ngày 16 tháng 2 năm 1953, Chủ tịch Hồ Chí Minh ký Sắc lệnh số 141-SL đổi Nha công an Trung ương thành Thứ Bộ Công an trực thuộc Hội đồng Chính phủ. Trần Quốc Hoàn ủy viên Ban Chấp hành Trung ương Đảng Cộng sản Việt Nam được cử giữ chức Thứ trưởng Thứ Bộ Công an. Thứ Bộ Công an có nhiệm vụ chống gián điệp, phản động ở trong nước để bảo vệ chính quyền dân chủ nhân dân, bảo vệ quân đội nhân dân, bảo vệ kinh tế quốc dân; bảo vệ biên giới, chống đặc vụ và gián điệp quốc tế; Bài trừ lưu manh trộm cướp, bài trừ các tệ nạn xã hội và giữ trật tự an ninh trong nhân dân; Quản trị các trại giam, giáo dục cải tạo phạm nhân. Thứ Bộ Công an gồm có: Văn phòng Thứ Bộ, Vụ Chấp pháp, Phòng Nhân sự, Cục cảnh vệ, Vụ Bảo vệ chính trị, Trường Công an, Vụ trị an hành chính.[6]

Cuộc họp Hội đồng Chính phủ từ ngày 27-29 tháng 8 năm 1953, dưới sự chủ tọa của Chủ tịch Hồ Chí Minh, đã quyết định đổi tên Thứ Bộ Công an thành Bộ Công an. Trần Quốc Hoàn được cử giữ chức Bộ trưởng Bộ Công an.